package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author RuiKnag
 * @create 2021-05-23-15:34
 * 优势是在一定范围内的整数进行排序，这属于牺牲空间换取时间的做法
 */
/*
* 计数排序不是基于比较的思想，而是对于一定范文内的数字进行排序，统计每一个有多少个数字，从小到大的放到一个新的数组中，
* 从而输出我们想要的这些数字，在这里我们要选取一些这样的数字进行排序。
*
* */
public class CountSort {
    static int findMax(int[] arr){
        int max=arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>max){
                max=arr[i];
            }
        }
        return max+1;
    }
    public static void sort(int[] arr){
        int[] count=new int[findMax(arr)];
        //统计每一个数字有多少
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }
        //进行一个计算，后面的数累加前面的数，这样每一位的数值就是对应i出现的最后的角标
        for (int i = 1; i <count.length ; i++) {
            count[i]=count[i]+count[i-1];
        }
        //这样可以保证排序的稳定
        int[] res=new int[arr.length];
        for (int i = arr.length-1; i >=0 ; i--) {
            res[--count[arr[i]]]=arr[i];
        }
        arr=res;
        System.out.println(Arrays.toString(arr));



    }

    public static void main(String[] args) {
        int[] arr=new int[]{5,6,6,5,5,5,5,5,7,7,7,7,7,7,6,6,6,6,2,2,2,2,2,3,3,3,3,3,4,3};

        sort(arr);


    }
}
